//
// Created by lxinp on 2022/8/30.
//

#ifndef DATASTRUCTURE_HASHTABLE_H
#define DATASTRUCTURE_HASHTABLE_H

#include <algorithm>
#include <vector>


template<typename K, typename V>
class HashTable {
public:
    class iterator;  // 声明了一个类？

    virtual ~HashTable();
    virtual void insert(const K& key, const V& value) = 0;
    virtual void remove(const K& key) = 0;  // remove the given key and associated data
    virtual V find(const K& key) const = 0;

    virtual bool key_exists(const K& key) const = 0;
    virtual bool is_empty() const { return elems == 0; }
    virtual size_t table_size() const { return size; }
    virtual void clear() = 0;  // empties the hash table (i.e. all key-value pairs)

    virtual V& operator[](const K& key) = 0;
    virtual iterator begin() const = 0;  // returns an iterator to the beginning of the HashTable
    virtual iterator end() const = 0;    // returns an iterator to the end of the HashTable

protected:
    size_t elems;  /* the current number of elements stored in the HashTable */
    size_t size;   /* the current size of the HashTable (total cells) */

    class HTIteratorImpl;  /* Implementation for the iterator */
    iterator make_iterator(HTIteratorImpl* impl) const { return iterator(impl); }

    inline bool should_resize() const { return static_cast<double>(elems) / size >= 0.7; }
    static const size_t primes[];    /* List of primes for resizing */
    size_t find_prime(size_t num);  /* finds the closest prime in our list to the given number */

private:
    virtual void resize_table() = 0;
};


/**
 * List of primes for resizing. "borrowed" from boost::unordered.
 */
template <typename K, typename V>
const size_t HashTable<K, V>::primes[]
        = {17ul,         29ul,         37ul,        53ul,        67ul,
           79ul,         97ul,         131ul,       193ul,       257ul,
           389ul,        521ul,        769ul,       1031ul,      1543ul,
           2053ul,       3079ul,       6151ul,      12289ul,     24593ul,
           49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
           1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
           50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
           1610612741ul, 3221225473ul, 4294967291ul};


template <typename K, typename V>
size_t HashTable<K, V>::find_prime(size_t num) {
    size_t len = sizeof(primes) / sizeof(size_t);  // number of prime numbers
    const size_t* first = primes;
    const size_t* last = primes + len;
    const size_t* prime = std::upper_bound(first, last, num);
    if (prime == last) --prime;
    return *prime;
}


//#include "ht_iterator.h"
#endif //DATASTRUCTURE_HASHTABLE_H
